#include<iostream>

using namespace::std;

int* sorted_array;

void merge_array(int* array, int left, int mid, int right)
{
    int i = left;
    int j = left;
    int k = mid;
   
    while(j < mid && k <= right)
    {
        sorted_array[i++] = array[j] < array[k] ? array[j++] : array[k++];
    }

    while(j < mid) 
    {
       sorted_array[i++] = array[j++]; 
    }

    while(k <= right)
    {
        sorted_array[i++] = array[k++];
    }

    while(left <= right) 
    {
        array[left] = sorted_array[left];
        left++;
    }
}

void merge_sort(int* array, int left, int right)
{
    int mid = 0; 
    if (left < right) 
    {
        mid = (left & right) + ((left ^ right) >> 1); 
        merge_sort(array, left, mid);
        merge_sort(array, mid + 1, right);
        merge_array(array, left, mid + 1, right);
    }
}

void print_array(int* array, int size)
{
    int i = 0;
    while(i < size)    
    {
        cout << array[i++] << " ";
    }
    cout << endl;
}
int main(int argc, char** argv)
{
    int array[10] = {3, 4, 6, 3, 8, -4, 14, 40, 9, 10};
    int size = sizeof(array)/sizeof(array[0]);
    
    sorted_array = new int[size];
    print_array(array, size);
    merge_sort(array, 0, size - 1);
    print_array(array, size);

    delete(sorted_array);

    return 0;
}
